package com.austin.leetcode.algorithm.LeetCodeArray;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * 在排序数组中查找元素的第一个和最后一个位置，如如数组不存在target返回-1
 *
 * @author Linbizhao
 * @since 2024/1/11 17:55
 */
@Slf4j
public class SolutionSearchRange {

    /**
     * int[] = [1,2,2,6,7], targetElement = 2 -> [1,2]
     * int[] = [1,2,2,6,7], targetElement = 8 -> [-1,-1]
     *
     * @param nums
     * @param targetElement
     * @return
     */
    public static int[] searchRange(int[] nums, int targetElement) {
        int len = nums.length;
        if (len == 0) {
            return new int[]{-1, -1};
        }

        int firstPosition = findFirstPosition(nums, targetElement);
        if (firstPosition == -1) {
            return new int[]{-1, -1};
        }

        int lastPosition = findLastPosition(nums, targetElement);
        return new int[]{firstPosition, lastPosition};
    }

    /**
     * 查询目标元素的开始位置
     *
     * @param nums
     * @param targetElement
     * @return
     */
    private static int findFirstPosition(int[] nums, int targetElement) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 计算中间位置的下标
            int mid = left + right >>> 1;
            if (nums[mid] < targetElement) {
                // 中间位置元素num[mid] < targetElement，下一轮搜索区间是[mid+1, right]
                left = mid + 1;
            } else if (nums[mid] == targetElement) {
                // 中间位置的元素num[mid] = targetElement，下一轮搜索的区间是[left, mid]
                right = mid;
            } else {
                // 中间位置的元素num[mid] > targetElement，下一轮搜索的区间是[left, mid - 1]
                right = mid - 1;
            }
        }

        if (nums[left] == targetElement) {
            return left;
        }

        return -1;
    }

    /**
     * 查询目标元素的结束位置
     *
     * @param nums
     * @param targetElement
     * @return
     */
    private static int findLastPosition(int[] nums, int targetElement) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 计算中间位置的下标，这里取中间数需要向上取整
            int mid = (left + right + 1) >>> 1;
            if (nums[mid] < targetElement) {
                // 中间位置元素num[mid] < targetElement，下一轮搜索区间是[mid+1, right]
                left = mid + 1;
            } else if (nums[mid] == targetElement) {
                // 中间位置的元素num[mid] = targetElement，下一轮搜索的区间是[mid, right]
                left = mid;
            } else {
                // 中间位置的元素num[mid] > targetElement，下一轮搜索的区间是[left, mid - 1]
                right = mid - 1;
            }
        }

        if (nums[left] == targetElement) {
            return left;
        }

        return -1;
    }

    public static void main(String[] args) {
        int left = 0;
        int right = 7;
        System.out.println(left + right >>> 1);
        System.out.println((left + right + 1) >>> 1);

        int[] nums = {5,7,7,8,8,10};
        int target = 6;

        log.info(Arrays.toString(Arrays.stream(searchRange(nums, target)).toArray()));
    }
}

